import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def fenwick_tree(n):
tree = [0] * (n + 1)
return tree
def get_sum0(i):
s = 0
while i > 0:
s += tree[i]
i -= i & -i
return s
def get_sum(s, t):
ans = 0 if s > t else get_sum0(t) - get_sum0(s - 1)
return ans
def add(i, x):
while i < len(tree):
tree[i] += x
i += i & -i
n = int(input())
p = list(map(int, input().split()))
c = [0] * (n + 1)
c[0] = -1
tree = fenwick_tree(n + 5)
ma = 0
for i in p:
if get_sum(i, n + 3) == 1:
c[ma] += 1
if ma < i:
c[i] -= 1
add(i, 1)
ma = max(ma, i)
ma = max(c)
for i in range(1, n + 1):
if ma == c[i]:
ans = i
break
print(ans)#include <bits/stdc++.h>
#define ii pair<int, int>
#define fs first
#define sc second
#define iii pair<int, ii>
#define fs3 fs
#define sc3 sc.fs
#define rd3 sc.sc
#define iiii pair<ii, ii>
#define fs4 fs.fs
#define sc4 fs.sc
#define rd4 sc.fs
#define fo4 sc.sc
#define db double
#define int long long
#define show(v) for (auto i : v) cout << i << " "; cout << endl;
#define showlr(v, l, r) for (int i = l; i <= r; i++) cout << v[i] << " "; cout << endl;
#define all(v) v.begin(), v.end()
#define Sort(v) sort(all(v));
#define Sortlr(v, l, r) sort(v + l, v + r);
#define rev(v) reverse(v.begin(), v.end());
#define revlr(v) reverse(v + l, v + r);
#define Unique(v) v.erase(unique(all(v)), v.end());
#define SUnique(v) Sort(v); Unique(v);
#define Fill(v) memset(v, 0, sizeof v);
#define Filldp(v) memset(v, -1, sizeof v);
#define mp(a, b) make_pair(a, b)
#define Has(v, l, r, val) binary_search(v + l, v + r, val)
#define forlr(i, l, r) for (int i = l; i <= r; i++)
#define forrl(i, r, l) for (int i = r; i >= l; i--)
#define pop_front_set(s) s.erase(s.begin());
#define pop_back_set(s) s.erase(s.rbegin());
#define erase_set(s, x) s.erase(s.find(x));
#define emptyQ(q) while (q.size()) q.pop();
#define emptyS(s) while (s.size()) s.pop();
#pragma GCC Optimize("O2")
#define endl "\n"
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define precise(x) cout << fixed << setprecision(x);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5 + 100;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int LOG = 25;
const int LINF = 1e15 + 100;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
ostream& operator << (ostream &os, ii a) {
os << a.fs << ' ' << a.sc;
return os;
}
ostream& operator << (ostream &os, iii a) {
os << a.fs3 << " " << a.sc3 << " " << a.rd3;
return os;
}
ostream& operator << (ostream &os, iiii a) {
os << a.fs4 << ' ' << a.sc4 << " " << a.rd4 << " " << a.fo4;
return os;
}
int ceil(int a, int b) {
return (a + b - 1) / b;
}
int binPow(int a, int b, int m) {
int prod = 1;
a %= m;
while (b) {
if (b & 1) prod = prod * a % m;
a = a * a % m;
b /= 2;
}
return prod;
}
int Pow(int a, int b) {
int prod = 1;
while (b) {
if (b & 1) prod *= a;
a *= a;
b /= 2;
}
return prod;
}
int sqr(int a) {
return a * a;
}
int len(int x) {
return log10(x) + 1;
}
void setIO(string s) {
if (s.empty()) return;
freopen((s + ".inp").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
int n, m, q, k;
int arr[N];
vector<int> adj[N];
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
struct BIT {
int bit[N];
void add(int u, int val) {
for (int idx = u; idx < N; idx += idx & -idx)
bit[idx] += val;
}
int get(int u) {
int res = 0;
for(int idx = u; idx > 0; idx -= idx & -idx)
res += bit[idx];
return res;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
};
int good[N], nearGood[N];
void solve() {
cin >> n;
int Mx = 0;
ii res = {-INF, -INF};
forlr(i, 1, n) cin >> arr[i];
forlr(i, 1, n) {
if (arr[i] > Mx) good[i] = 1;
Mx = max(Mx, arr[i]);
}
BIT bit, cnt1;
forlr(i, 1, n) {
if (bit.get(arr[i] + 1, n) == 1) cnt1.add(arr[i], 1);
bit.add(arr[i], 1);
}
forlr(i, 1, n) {
int add = cnt1.get(1, arr[i] - 1) - good[i];
res = max(res, {add, -arr[i]});
if (cnt1.get(arr[i], arr[i]) == 1) cnt1.add(arr[i], -1);
}
cout << -res.sc << endl;
}
signed main() {
fastIO;
int T = 1;
bool multiTest = 0;
if (multiTest) cin >> T;
while (T--) solve();
}
274. H-Index | 260. Single Number III |
240. Search a 2D Matrix II | 238. Product of Array Except Self |
229. Majority Element II | 222. Count Complete Tree Nodes |
215. Kth Largest Element in an Array | 198. House Robber |
153. Find Minimum in Rotated Sorted Array | 150. Evaluate Reverse Polish Notation |
144. Binary Tree Preorder Traversal | 137. Single Number II |
130. Surrounded Regions | 129. Sum Root to Leaf Numbers |
120. Triangle | 102. Binary Tree Level Order Traversal |
96. Unique Binary Search Trees | 75. Sort Colors |
74. Search a 2D Matrix | 71. Simplify Path |
62. Unique Paths | 50. Pow(x, n) |
43. Multiply Strings | 34. Find First and Last Position of Element in Sorted Array |
33. Search in Rotated Sorted Array | 17. Letter Combinations of a Phone Number |
5. Longest Palindromic Substring | 3. Longest Substring Without Repeating Characters |
1312. Minimum Insertion Steps to Make a String Palindrome | 1092. Shortest Common Supersequence |